package com.vic.datastructure.sort.quick;

//import cn.hutool.core.util.RandomUtil;

import java.util.Random;

public class QuickSortTest2 {

    public static void main(String[] args) {
        int [] arr = {132,5,6,7,223,78,13,89,22};

        quickSort(arr, 0, arr.length - 1);

    }

    private static void quickSort(int[] arr, int l, int r) {

        if(r <= l) {
            return;
        }

        int q = partition(arr, l, r);
        quickSort(arr, l, q - 1);
        quickSort(arr, q + 1, r);
    }

    private static int partition(int[] arr, int l, int r) {
//        int p = RandomUtil.randomInt(l, r + 1);

        int p = new Random().nextInt(r + 1) + l;

        swap(arr[p], arr[r]);

        int i = l;
        for(int j = l; j <= r - 1; j++) {
            if(arr[j] <= arr[r]) {
                swap(arr[i], arr[j]);
                i = i + 1;
            }
        }
        swap(arr[i], arr[r]);
        return i;
    }

    private static void swap(int a, int b) {


    }


}
